package Z代码随想录.数组;

public class Leetcode27 {
    // 移除元素,原地移除所有等于val的元素，并返回新数组的元素个数

    // 方法一，暴力求解，双层循环，第一层遍历数组找到等于val的元素，第二层用来负责将后面的元素往前挪
    // 时间复杂度 O(n^2)
    // 在移动的过程中，注意数组的 size 也是在时刻变化的，找到一个数组的长度也缩小一个
    public static int removeElement(int[] nums, int val) {
        int i = 0;
        int j = 0;
        int size = nums.length;
        for (i = 0; i < size; i++) {
            // 找到数组中等于 val的值，将后面的值全部往前挪一个位置
            if (nums[i] == val) {
                // 如果是最后一个元素和val相等，j + 1 就会越界，此时就不会进入循环
                // 此处要考虑第一个元素 和 val 相等时候，防止数组越界情况
                for (j = i + 1; j < size; j++) {
                    // 依次从后往前挪
                    nums[j - 1] = nums[j];
                }
                i--;// 防止少判断一个元素，因为数组已经整体往前挪了一个位置
                size--;  // 挪完以后，元素相当于少一个
            }
        }
        return size;
    }

    // 第二种方法，使用快慢指针！
    // 时间复杂度 O(n)
    public static int removeElement2(int[] nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            // 只要快指针指向的元素不等于 val 就赋值
            if (nums[fastIndex] != val){
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        // 遍历结束后，此时 slowIndex 就是元素的个数
        return slowIndex;
    }

    public static void main(String[] args) {
        int[] array = new int[]{4, 2, 2, 3};
        System.out.println(removeElement(array, 3));
    }
}
